package com.jwetherell.my;

import java.util.Arrays;

/**
 * In Array implementation of BinaryHeap, we don't store data in zeroth index
 * 
 * The elements of BinaryHeap are stored in the array according to the
 * BFS of BinaryHeap. Means if we do BFS on logical-binary-tree of BinaryHeap,
 * then the elements will go into the array with that order only i.e starting with root,
 * then all nodes from left-to-right in the next level and so on.
 * 
 * So root will be stored at index [1]
 * 
 */
public class BinaryHeap<T extends Comparable<T>> {

	public static final int MINIMUM_SIZE = 10;

	private Object[] data;
	private int currentSize = 0;

	private boolean isMinHeap;

	public BinaryHeap() {
		this(MINIMUM_SIZE, false);
	}

	public BinaryHeap(int size, boolean isMinHeap) {
		this.data = new Object[size + 1];
		this.isMinHeap = isMinHeap;
	}

	@SuppressWarnings("unchecked")
	public void insertThroughBottomUpApproach(T value) {
		if (isFull()) {
			grow();
		}
		
		if (currentSize == 0) {// no data in the heap
			data[1] = value;
			currentSize++;
			return;
		}

		int indexToStoreAt = currentSize + 1;
		data[indexToStoreAt] = value; // inserted the new value at the right most empty node at last level
		
		// heapify
		int parentIndex = getParentIndex(indexToStoreAt);
		int childIndex = indexToStoreAt;
		
		while (parentIndex >= 1 && isParentGreaterThanChild(parentIndex, childIndex)) {
			swap(parentIndex, childIndex);
			childIndex = parentIndex;
			parentIndex = getParentIndex(childIndex);
		}
		
		currentSize++;
		
	}

	@SuppressWarnings("unchecked")
	private void swap(int parentIndex, int childIndex) {
		T temp = (T)data[parentIndex];
		data[parentIndex] = data[childIndex];
		data[childIndex] = temp;
	}

	@SuppressWarnings("unchecked")
	private boolean isParentGreaterThanChild(int parentIndex, int childIndex) {
		T parent = (T)data[parentIndex];
		T child = (T)data[childIndex];
		return parent.compareTo(child) == 1;
	}

	private int getParentIndex(int childIndex) {
		return (int)Math.floor(childIndex / 2);
	}
	

	public void insertThroughTopDownApproach(T value) {
		
		T root = (T)data[1];
		
		if (root == null)
			data[1] = value;
		
		
		
		data[currentSize] = value;
//		heapify(currentSize);
	}

	private boolean isFull() {
		return this.data.length == (this.currentSize + 1); // +1 b'coz zeroth index is not used
	}

	private void grow() {
		if (data.length <= (currentSize + 1))
			Arrays.copyOf(data, data.length * 2);
	}
	
	public void printHeap() {
		for (int i = 1; i <= currentSize; i++)
			System.out.println(data[i]);
	}
	
}
